package tree;

import util.Node;

import java.util.Stack;

/**
 * @BelongsProject: leetcode
 * @BelongsPackage: tree
 * @author: 肖
 * @date: 2022/1/28 9:38
 * @Description: 搜索二叉树
 * @since JDK 11
 */

public class TestBST {
    public static class ReturnData {
        public boolean isBST;
        public int min;
        public int max;

        public ReturnData(boolean isBST, int min, int max) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
        }
    }

    public static ReturnData process(Node root) {
        if (root == null) {
            return null;
        }
        ReturnData leftData = process(root.left);
        ReturnData rightData = process(root.right);
        int min = root.value;
        int max = root.value;
        if (leftData != null) {
            min = Math.min(min, leftData.min);
            max = Math.max(max, leftData.max);
        }
        if (rightData != null) {
            min = Math.min(min, rightData.min);
            max = Math.max(max, rightData.max);
        }
        boolean isBST = true;
        if (leftData != null && (!leftData.isBST || leftData.max >= root.value)) {
            isBST = false;
        }
        if (rightData != null && (!rightData.isBST || root.value >= rightData.max)) {
            isBST = false;
        }
        return new ReturnData(isBST, min, max);
    }


    public static int preValue = Integer.MIN_VALUE;

    public static boolean isBST(Node head) {
        if (head == null) return true;
        boolean isLeftBST = isBST(head.left);
        if (!isLeftBST) {
            return false;
        }
        if (head.value <= preValue) {
            return false;
        } else {
            preValue = head.value;
        }
        return isBST(head.right);
    }

    //    中序遍历
    public static void inOrderRecur(Node head) {
        if (head == null) return;
        inOrderRecur(head.left);
        System.out.println(head.value + "");
        inOrderRecur(head.right);
    }

    //    非递归
    public static void inOrderUnRecur(Node head) {
        System.out.println("In-order:");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    head = stack.pop();
                    System.out.println(head.value + "");
                    head = head.right;
                }
            }
        }


    }
}
